// 给你一个数组 prices ，其中 prices[i] 是商店里第 i 件商品的价格。
// 商店里正在进行促销活动，如果你要买第 i 件商品，
// 那么你可以得到与 prices[j] 相等的折扣，其中 j 是满足 j > i 且 prices[j] <= prices[i] 的 最小下标 ，
// 如果没有满足条件的 j ，你将没有任何折扣。

// 解法1 o n^2 
var finalPrices1 = function (prices) {
  let res = [];
  for (let i = 0; i < prices.length; i++) {
    let flag = false;
    for (let j = i + 1; j < prices.length; j++) {
      if (prices[j] <= prices[i]) {
        res.push(prices[i] - prices[j]);
        flag = true;
        break;
      }
    }
    if (!flag) {
      res.push(prices[i])
    }
  }
  return res;
};

// 想个解法2好吗？ O(N)?
var finalPrices2 = function (prices) {
  let currentMinVal = prices[prices.length - 1];
  let res = [];
  res.unshift(currentMinVal)
  for (let i = prices.length - 2; i >= 0; i--) {
    if (prices[i] >= prices[i + 1]) {
      res.unshift(prices[i] - prices[i + 1]);
    } else if (prices[i] >= currentMinVal) {
      res.unshift(prices[i] - currentMinVal);
    } else {
      res.unshift(prices[i]);
      currentMinVal = prices[i]
    }
  }
  throw new Error('抛出异常，程序结束')
  return res;
};
// console.log(finalPrices2([8, 4, 6, 2, 3]));
// console.log(finalPrices2([1, 2, 3, 4, 5]));
// console.log(finalPrices2([5, 4, 10, 2, 6, 1, 1, 1, 9, 1]));
console.log(finalPrices2(123));